#include <iostream>
#include <stdio.h>
#include <cmath>
#include <map>
#include <memory>
#include <vector>
#include <functional>
// #include <lapacke.h>
// #include <json/json.h>
// #include "lapacke_utils.h"
#include <fstream>
#include <sstream>
#include <assert.h>
#include <cstdlib>
#include <string>
#include <chrono>
using namespace std;
using Real = double;
class polynomial
{
public:
	vector<Real> coeff;
	int degree;
	polynomial()
	{
		vector<Real> _coeff(0);
		coeff = _coeff;
		degree = 0;
	}
	polynomial(vector<Real> _coeff, int _degree)
	{
		coeff = _coeff;
		degree = _degree;
	}
	friend polynomial operator+(polynomial a, polynomial b)
	{
		int a1 = a.degree;
		vector<Real> a2 = a.coeff;
		int b1 = b.degree;
		vector<Real> b2 = b.coeff;
		int n;
		if (a1 >= b1)
			n = a1;
		else
			n = b1;
		vector<Real> x(n + 1);
		for (int i = 0; i <= n; i++)
		{
			if (i <= a1 && i <= b1)
				x[i] = a2[i] + b2[i];
			else if (i <= a1 && i > b1)
				x[i] = a2[i];
			else
				x[i] = b2[i];
		}
		polynomial c;
		c.degree = n;
		c.coeff = x;
		return c;
	}
	friend polynomial operator*(Real x, polynomial a)
	{
		int n = a.degree;
		vector<Real> g = a.coeff;
		int m = n;
		vector<Real> s(m + 1);
		for (int i = 0; i <= m; i++)
			s[i] = x * g[i];
		polynomial c;
		c.degree = m;
		c.coeff = s;
		return c;
	}
	friend polynomial operator-(polynomial a, polynomial b)
	{
		polynomial A;
		polynomial c = -1 * b;
		polynomial d = a * c;
		return d;
	}
	friend polynomial operator*(polynomial a, polynomial b)
	{
		int a1 = a.degree;
		vector<Real> a2 = a.coeff;
		int b1 = b.degree;
		vector<Real> b2 = b.coeff;
		int c = a1 + b1;
		vector<Real> d(c + 1);
		for (int i = 0; i <= c; i++)
		{
			d[i] = 0;
			for (int j = 0; j <= i; j++)
			{
				if (i - j <= b1 && j <= a1)
					d[i] += a2[j] * b2[i - j];
			}
		}
		polynomial e;
		e.degree = c;
		e.coeff = d;
		return e;
	}
	polynomial interpolate(Real first, vector<Real> root)
	{
		int n = root.size();
		vector<Real> a0 = {-root[0], 1.0};
		vector<Real> a1 = {-root[0], 1.0};
		polynomial a;
		polynomial b;
		int p = 1;
		a = polynomial(a0, p);
		for (int i = 1; i < n; i++)
		{
			a1[0] = -root[i];
			b = polynomial(a1, p);
			a = a * b;
		}
		a = first * a;
		return a;
	}
	Real pointvalue(Real x, polynomial a)
	{
		int a1 = a.degree;
		vector<Real> a2 = a.coeff;
		Real c = 0;
		for (int i = 0; i <= a1; i++)
			c += a2[i] * pow(x, i);
		return c;
	}
	polynomial derivate(polynomial a)
	{
		int a1 = a.degree;
		vector<Real> a2 = a.coeff;
		int n;
		if (a1 == 0)
			n = 0;
		else
			n = a1 - 1;
		vector<Real> x(n + 1);
		if (a1 != 0)
		{
			for (int i = 0; i <= n; i++)
				x[i] = a2[i + 1] * (i + 1);
		}
		else
			x[0] = 0;
		polynomial e;
		e.degree = n;
		e.coeff = x;
		return e;
	}
	Real integration(polynomial poly, Real a, Real b)
	{
		Real key = 0;
		vector<Real> _coeff = poly.coeff;
		int n = poly.degree;
		for (int i = 0; i <= n; i++)
		{
			key += 1.0 * _coeff[i] * (pow(b, n + 1) - pow(a, n + 1)) / (i + 1);
		}
		return key;
	}
};